/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/15
 * \* Time: 22:12
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 二叉树中的最大路径和 {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
    int max=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root){
        Maxval(root);
        return max;
    }

    public int Maxval(TreeNode node){
        if(node==null){
            return 0;
        }

        int leftVal=Math.max(Maxval(node.left),0);
        int rightVal=Math.max(Maxval(node.right),0);
        int tmp=node.val+leftVal+rightVal;

        //更新结果
        max=Math.max(max,tmp);
        return node.val+Math.max(leftVal,rightVal);
    }
}